{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Fibonnaci Sequence\n",
    "\n",
    "## Problem Statement\n",
    "\n",
    "Implement a [Fibonnaci Sequence](https://en.wikipedia.org/wiki/Fibonacci_number) in three different ways:\n",
    "\n",
    "* Recursively\n",
    "* Dynamically (Using Memoization to store results)\n",
    "* Iteratively\n",
    "\n",
    "Remember that a fibonacci sequence: 0,1,1,2,3,5,8,13,21,... starts off with a base case checking to see if n = 0 or 1, then it returns 1. \n",
    "\n",
    "Else it returns fib(n-1)+fib(n+2)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Recursively\n",
    "\n",
    "The recursive solution is exponential time Big-O , with O(2^n). However, its a very simple and basic implementation to consider:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fib_rec(n):\n",
    "    \n",
    "    # Base Case\n",
    "    if n == 0 or n == 1:\n",
    "        return n\n",
    "    \n",
    "    # Recursion\n",
    "    else:\n",
    "        return fib_rec(n-1) + fib_rec(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fib_rec(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Dynamically\n",
    "\n",
    "In the form it is implemented here, the cache is set beforehand and is based on the desired **n** number of the Fibonacci Sequence. Note how we check it the cache[n] != None, meaning we have a check to know wether or not to keep setting the cache (and more importantly keep cache of old results!)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Instantiate Cache information\n",
    "n = 10\n",
    "cache = [None] * (n + 1)\n",
    "\n",
    "\n",
    "def fib_dyn(n):\n",
    "    \n",
    "    # Base Case\n",
    "    if n == 0 or n == 1:\n",
    "        return n\n",
    "    \n",
    "    # Check cache\n",
    "    if cache[n] != None:\n",
    "        return cache[n]\n",
    "    \n",
    "    # Keep setting cache\n",
    "    cache[n] = fib_dyn(n-1) + fib_dyn(n-2)\n",
    "    \n",
    "    return cache[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fib_dyn(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Iteratively\n",
    "\n",
    "In this solution we can take advantage of Python's tuple unpacking!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fib_iter(n):\n",
    "    \n",
    "    # Set starting point\n",
    "    a = 0\n",
    "    b = 1\n",
    "    \n",
    "    # Follow algorithm\n",
    "    for i in range(n):\n",
    "        \n",
    "        a, b = b, a + b\n",
    "        \n",
    "    return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "28657"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fib_iter(23)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Test Your Solution\n",
    "\n",
    "Run the cell below to test your solutions, simply uncomment the solution functions you wish to test!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Passed all tests.\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "UNCOMMENT THE CODE AT THE BOTTOM OF THIS CELL TO SELECT WHICH SOLUTIONS TO TEST.\n",
    "THEN RUN THE CELL.\n",
    "\"\"\"\n",
    "\n",
    "from nose.tools import assert_equal\n",
    "\n",
    "class TestFib(object):\n",
    "    \n",
    "    def test(self,solution):\n",
    "        assert_equal(solution(10),55)\n",
    "        assert_equal(solution(1),1)\n",
    "        assert_equal(solution(23),28657)\n",
    "        print 'Passed all tests.'\n",
    "# UNCOMMENT FOR CORRESPONDING FUNCTION\n",
    "t = TestFib()\n",
    "\n",
    "t.test(fib_rec)\n",
    "#t.test(fib_dyn) # Note, will need to reset cache size for each test!\n",
    "#t.test(fib_iter)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Conclusion\n",
    "\n",
    "Hopefully this interview question served as a good excercise in exploring recursion, dynamic programming, and iterative solutions for a single problem! Its good to work through all three because in an interview a common question may just begin with requesting a recursive solution and then checking to se if you can implement the other forms!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
